package com.ggqq.day330;

public class MostLongSubStr {
    public static void main(String[] args) {
        MostLongSubStr mostLongSubStr = new MostLongSubStr();
        System.out.println(mostLongSubStr.longestPalindrome("babad"));

    }
    public String longestPalindrome(String s){
        /*int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans ="";
        for(int l=0;l<n;l++){
            for(int i=0;i+l<n;i++){
                int j = i+1;
                if(l==0){
                   dp[i][j]=true;
                }else if( l == 1){
                    dp[i][j] = (s.charAt(i)==s.charAt(j));
                }else{
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]);
                }
                if(dp[i][j] && l+1>ans.length()){
                    ans = s.substring(i,i+l+1);
                }
            }
        }
        return ans;*/
        //方法2：中心扩散算法
        if(s == null || s.length()<1){
            return "";
        }
        int start = 0,end=0;
        for(int i=0;i<s.length();i++){
            int len1 = expendAroundCenter(s,i,i);//子串长度为1时扩展
            int len2 = expendAroundCenter(s,i,i+1);//子串长度为2时扩展
            int len = Math.max(len1,len2);
            if(len > end-start){
                start = i - (len-1)/2;
                end = i+len/2;
            }
        }
        return s.substring(start,end+1);
    }

    private int expendAroundCenter(String s,int left,int right) {
        while(left>=0 && right <s.length() && s.charAt(left)==s.charAt(right)){
            left--;  //中心向外扩散
            right++;
        }
        return right-left-1;//长度
    }
}
